{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def wordvec(n):\n",
    "    limbs = []\n",
    "    while n > 0:\n",
    "        limbs += [n % 2**64]\n",
    "        n >>= 64\n",
    "    return limbs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def litteral(n):\n",
    "    return '[' + ', '.join(['0x{:016x}u64'.format(x) for x in wordvec(n)]) + ']'\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "numerator = random.randrange(0, 2**256*divisor - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0x9c2bcebfa9cca2c6u64, 0x274e154bb5e24f7au64, 0xe1442d5d3842be2bu64, 0xf18f5adfd420853fu64, 0x04ed6127eba3b594u64, 0xc5c179973cdb1663u64, 0x7d7f67780bb268ffu64, 0x0000000000000003u64]\n"
     ]
    }
   ],
   "source": [
    "print(litteral(numerator))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "divisor = random.randrange(2**150, 2**200)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0x0181880b078ab6a1u64, 0x62d67f6b7b0bda6bu64, 0x92b1840f9c792dedu64, 0x0000000000000019u64]\n"
     ]
    }
   ],
   "source": [
    "print(litteral(divisor))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "quotient = numerator // divisor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0x9128464e61d6b5b3u64, 0xd9eea4fc30c5ac6cu64, 0x944a2d832d5a6a08u64, 0x22f06722e8d883b1u64]\n"
     ]
    }
   ],
   "source": [
    "print(litteral(quotient))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "remainder = numerator % divisor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0x1dfa5a7ea5191b33u64, 0xb5aeb3f9ad5e294eu64, 0xfc710038c13e4eedu64, 0x000000000000000bu64]\n"
     ]
    }
   ],
   "source": [
    "print(litteral(remainder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_n = (2**64 - 1) * 2**127"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x7fffffffffffffff'"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(max_n // 2**128)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9223372036854775807"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0x7fffffffffffffff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11798059056785105239005283356123191317202602344528712841934114391309054742122373953814119876411222892364613880599086749005694767641207115788542350244223258"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r1 = numerator - 0x39f8f6254252914d * divisor * 2**(64 * 3)\n",
    "r1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[0xede50f50e2f4991au64, 0x305e6a43c656da59u64, 0x307e1e779ae14938u64, 0xec84e19410022738u64, 0x76a3b33f6891301du64, 0x6be8a080044521e6u64, 0xc907d639dd1697e9u64, 0xe143b61ef845c10au64]'"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "litteral(r1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a =  0x2fff7097162a629c\n",
      "b =  0xf471b33a3fa9dc84\n"
     ]
    }
   ],
   "source": [
    "b = 0\n",
    "d = 0x33078428bf2556b3\n",
    "n = 0xfb8fa94ba5d6d973\n",
    "q = 0x39f8f6254252914d\n",
    "A = n - (q * d + b)\n",
    "assert abs(A) < 2**128\n",
    "a = A % 2**64\n",
    "b = (A % 2**128) // 2**64\n",
    "print('a = ', hex(a))\n",
    "print('b = ', hex(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a =  0x6fc526fc8d5c2b0e\n",
      "b =  0xe5a3ca7ded870292\n"
     ]
    }
   ],
   "source": [
    "b = 0xf471b33a3fa9dc84\n",
    "d = 0x7467530ac1da99d8\n",
    "n = 0x998ac5b264c5ec82\n",
    "q = 0x39f8f6254252914d\n",
    "A = n - (q * d - b)\n",
    "assert abs(A) < 2**128\n",
    "a = A % 2**64\n",
    "b = (A % 2**128) // 2**64\n",
    "print('a = ', hex(a))\n",
    "print('b = ', hex(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 0x6f1480e63854afa41868b9a7d418e9c64edef514135f5899e72530a3d4e91ea3\n",
    "b = 0x3ba5ddaec5090ef0b87126f34ee28533ffb08af4108f9aeaa62b65900d2a62bb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a // b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x1bc520398e152be90'"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(0x00000000000000006f1480e63854afa4 << 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0xf7ffffffffffffef'"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(-0x800000000000011 % 2**64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 2**64 - 1\n",
    "b = 2**64 - 1\n",
    "c = 2**64 - 1\n",
    "d = 2**64 - 1\n",
    "e = 2**64 - 1\n",
    "f = 2**64 - 1\n",
    "m = a + (b * c) + (d * e) + f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x1fffffffffffffffe0000000000000000'"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-130-1cb810fcdf23>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mm\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0;36m128\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "assert m < 2**128"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mul_red(x, y):\n",
    "    A = 0\n",
    "    for i in range(4):\n",
    "        u = a + (x >> (64 * i)) * y * (-1) % 2**64\n",
    "        print(hex(u))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mul_red()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'modinv' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-147-930e3466f3cf>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0x0548c135e26faa9c977fb2eda057b54b2e0baa9a77a0be7c80278f4f03462d4c\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0my\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0x024385f6bebc1c496e09955db534ef4b1eaff9a78e27d4093cfa8f7c8f886f6b\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mr\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0my\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mmodinv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0;36m256\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mprime\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m%\u001b[0m \u001b[0mprime\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'modinv' is not defined"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
